/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* getmid(ListNode*head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != nullptr&&fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    ListNode* myreverse(ListNode* head)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        ListNode* next = nullptr;
        while(cur!=nullptr)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }//翻转head后的节点并且返回新的头节点
    void reorderList(ListNode* head) 
    {
        if(head == nullptr)
        {
            return;
        }
        // 这道题目的解法为首先找到原链表的中间节点，然后将从中间节点往后的节点翻转，这样就得到了两个链表
        // 其中就具有了两个heda(heda1和head2)[head2为翻转后的新链表的头节点]然后将head1->next = head2
        // 然后再让head1等于原来的next节点，以及让head2等于原来的next，这样不断循环直到head2等于中间节点，或者
        // head2->next等于nullptr
        //下面就来解决这道题目
        ListNode* mid = getmid(head);//通过快慢指针得到中间节点
        //现在就是两个链表了，然后就是要将中间节点往后的节点进行翻转
        //然后就是使用将heada1的next指向head2然后让head1等于原来的下一个节点，head2等于原来的下一个节点
        ListNode* head1 = head;
        ListNode* head2 = myreverse(mid);
        while(head2->next)
        {
            ListNode* nxt1 = head1->next;
            ListNode* nxt2 = head2->next;
            head1->next = head2;
            head2->next = nxt1; 
            head1 = nxt1;
            head2 = nxt2;
        }
    }
};